public class MyLinklist implements Linklist{
    public static class node{
        public int val;//节点的值
        public node side;//下一个节点的地址

        public node(int val) {
            this.val = val;
        }
    }
    public static node Head;
    @Override
    public void addFirst(int data) {
        node list = new node(data);

            list.side = Head;
            Head = list;

    }//头插法

    @Override
    public void addLast(int data) {
        node node = new node(data);
        node cur = Head;
        if (cur == null){
            addFirst(data);
            return;
        }
        while (cur.side != null){
            cur = cur.side;
        }
        cur.side = node;
    }//尾插法

    @Override
    public void addIndex(int index, int data) {
        node node = new node(data);
        if (index < 0 || index > size()){
            throw new IndexException("index位置异常");
        }
        if (index == 0){
            addFirst(data);
            return;
        }
        if (index == size()){
            addLast(data);
            return;
        }
        node cur = Head;
        node pur = Head.side;
        for (int i = 1; i < index; i++) {
            cur = cur.side;
            pur = pur.side;
        }
        node.side = pur;
        cur.side = node;

    }//任意位置插⼊第⼀个数据节点为0 号下标

    @Override
    public boolean contains(int key) {
        node cur = Head;
        while (cur != null){
            if (cur.val == key){
                return true;
            }
            cur =cur.side;
        }
        return false;
    }//查找是否包含关键字key是否在单链表当中

    @Override
    public void remove(int key) {
        node cur = Head;
        node pur = Head.side;
        if (cur.val ==key){
            Head = Head.side;
            cur = Head;
            pur = Head.side;
        }
        while (pur != null){
            if (pur.val == key){
                cur.side = pur.side;
            }
            cur = cur.side;
            pur = pur.side;
        }
    }//删除第⼀次出现关键字为 key的节点

    @Override
    public void removeAllKey(int key) {
        node cur = Head;
        node pur = Head.side;
        if (cur.val ==key){
            Head = Head.side;
            cur = Head;
            pur = Head.side;
        }
        while (pur != null){
            if (pur.val == key){
                cur.side = pur.side;
                pur = pur.side;
                continue;
            }
            cur = cur.side;
            pur = pur.side;
        }
    }//删除所有值为key的节点

    @Override
    public int size() {
        node cur = Head;
        int size = 0;
        while (cur != null){
            size++;
            cur = cur.side;
        }
        return size;
    }//得到单链表的⻓度

    @Override
    public void clear() {
        Head = null;
    }//清空链表

    @Override
    public void display() {
        node cur = Head;

        while (cur != null){
            System.out.print(cur.val+" ");

            cur = cur.side;
        }
    }//展览链表

    @Override
    public void reversal() {
        node pur =Head.side.side;
        node cur = Head.side;
        node nur = Head;
        nur.side = null;
        while (pur != null){
            cur.side = nur;
            nur = cur;
            cur = pur;
            pur = pur.side;
            if (pur == null){
                cur.side = nur;
            }
        }
        Head =cur;
    }// 反转⼀个单链表

    @Override
    public int middle() {
        node cur = Head;
        node pur = Head;
        if (size() %2 == 1){
            while (pur.side != null){
                cur = cur.side;
                pur = pur.side.side;
            }
            return cur.val;
        }
        if (size() %2 == 0){
            while (pur != null){
                cur = cur.side;
                pur = pur.side.side;
            }
            return cur.val;
        }
        return 0;
    }//返回链表的中间结点

    @Override
    public int backwards(int k) {
        node cur = Head;
        int i = k;
        if(k <= 0 || k > size()){
            System.out.println("k的位置不合理");
            return -1;
        }
        if (Head == null){
            System.out.println("链表为空");
        }
        for (int j = 0; j < size() - k; j++) {
            cur = cur.side;
        }
        return cur.val;
    }//输出该链表中倒数第k个结点


}

